{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Furthest Building You Can Reach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: furthestBuilding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可以到达的最远建筑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>heights</code> ，表示建筑物的高度。另有一些砖块 <code>bricks</code> 和梯子 <code>ladders</code> 。</p>\n",
    "\n",
    "<p>你从建筑物 <code>0</code> 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。</p>\n",
    "\n",
    "<p>当从建筑物 <code>i</code> 移动到建筑物 <code>i+1</code>（下标<strong> 从 0 开始 </strong>）时：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果当前建筑物的高度 <strong>大于或等于</strong> 下一建筑物的高度，则不需要梯子或砖块</li>\n",
    "\t<li>如果当前建筑的高度 <strong>小于</strong> 下一个建筑的高度，您可以使用 <strong>一架梯子</strong> 或 <strong><code>(h[i+1] - h[i])</code> 个砖块</strong></li>\n",
    "</ul>\n",
    "如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标<strong> 从 0 开始 </strong>）。\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/31/q4.gif\" style=\"width: 562px; height: 561px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>从建筑物 0 出发，你可以按此方案完成旅程：\n",
    "- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2\n",
    "- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7\n",
    "- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6\n",
    "- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9\n",
    "无法越过建筑物 4 ，因为没有更多砖块或梯子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [14,3,19,3], bricks = 17, ladders = 0\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= heights.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= heights[i] <= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 <= bricks <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 <= ladders <= heights.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [furthest-building-you-can-reach](https://leetcode.cn/problems/furthest-building-you-can-reach/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [furthest-building-you-can-reach](https://leetcode.cn/problems/furthest-building-you-can-reach/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,7,6,9,14,12]\\n5\\n1', '[4,12,2,7,3,18,20,3,19]\\n10\\n2', '[14,3,19,3]\\n17\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        # 优先队列 + 贪心\n",
    "        # n: 记录建筑物的个数\n",
    "        n = len(heights)\n",
    "        queue = []\n",
    "        # 使用砖块的数量\n",
    "        brick_num = 0\n",
    "        # 计算每两个建筑物之间的高度差\n",
    "        for i in range(1,n):\n",
    "            res = heights[i]-heights[i-1]\n",
    "            # 如果后面的比前面的高【即下一个建筑物比当前建筑物高】\n",
    "            if res>0:\n",
    "                # 把当前高度差存进去,留下与梯子数相等的最大的高度差\n",
    "                # 想要对最大的高度差使用梯子，因为一个梯子的作用抵得过许多砖头\n",
    "                heapq.heappush(queue,res)\n",
    "                if len(queue)>ladders:\n",
    "                    # 弹出队列的要使用砖块补上\n",
    "                    brick_num += heapq.heappop(queue)\n",
    "                if brick_num > bricks:\n",
    "                    # 如果此时砖块数量也不够了,此时只能返回上一个建筑物的下标，当前的建筑物过不去了\n",
    "                    return i-1\n",
    "        # 最多到达n-1【最后一个】\n",
    "        return n-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        #感觉是ologn复杂度 二分答案再加上遍历\n",
    "        l = 0\n",
    "        n = len(heights)\n",
    "        r = n - 1\n",
    "        def is_t(mid):\n",
    "            lis = []\n",
    "            for i in range(1, mid+1):\n",
    "                if (res:=heights[i] - heights[i-1]) > 0:\n",
    "                    lis.append(res)\n",
    "            lis.sort(reverse=True)\n",
    "            # print(lis)\n",
    "            if sum(lis[ladders:]) <= bricks:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l+r)>>1\n",
    "            #判断到这个位置能不能取得到\n",
    "            if is_t(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        q = []\n",
    "        b = 0\n",
    "        for i in range(1, n):\n",
    "            d = heights[i] - heights[i-1]\n",
    "            if d > 0:\n",
    "                heappush(q, d)\n",
    "\n",
    "                if len(q) > ladders:\n",
    "                    b += heappop(q)\n",
    "                if b > bricks:\n",
    "                    return i - 1\n",
    "        return n - 1\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        laddre_on = []\n",
    "        brick_remain = bricks\n",
    "\n",
    "        for i in range(1,len(heights)):\n",
    "            if heights[i-1] >= heights[i]:\n",
    "                continue\n",
    "            \n",
    "            diff = heights[i] - heights[i-1]\n",
    "            if len(laddre_on) < ladders:\n",
    "                heappush(laddre_on,diff)\n",
    "            elif len(laddre_on) > 0 and diff > laddre_on[0]:\n",
    "                brick_remain -= heappop(laddre_on)\n",
    "                if brick_remain <0 : return i-1;\n",
    "                heappush(laddre_on,diff)\n",
    "            else:\n",
    "                brick_remain -= diff\n",
    "                if brick_remain < 0: return i-1\n",
    "        return len(heights) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        used_la = []\n",
    "        res = 0\n",
    "        i = 1\n",
    "        while i<n:\n",
    "            if heights[i]>heights[i-1]:\n",
    "                cur_diff = heights[i]-heights[i-1]\n",
    "                if ladders>0:\n",
    "                    ladders -= 1\n",
    "                    heapq.heappush(used_la, cur_diff)\n",
    "                else:\n",
    "                    if len(used_la)==0 or used_la[0]>=cur_diff:\n",
    "                        if bricks>=cur_diff:\n",
    "                            bricks -= cur_diff\n",
    "                        else:\n",
    "                            break\n",
    "                    else:\n",
    "                        if bricks>=used_la[0]:\n",
    "                            bricks -= used_la[0]\n",
    "                            heapq.heappop(used_la)\n",
    "                            heapq.heappush(used_la, cur_diff)\n",
    "                        else:\n",
    "                            break\n",
    "                pass\n",
    "            res = i\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "\n",
    "        q = list()\n",
    "        sumH = 0\n",
    "        for i in range(1, n):\n",
    "            deltaH = heights[i] - heights[i - 1]\n",
    "            if deltaH > 0:\n",
    "                heapq.heappush(q, deltaH)\n",
    "                if len(q) > ladders:\n",
    "                    sumH += heapq.heappop(q)\n",
    "                if sumH > bricks:\n",
    "                    return i - 1\n",
    "\n",
    "        return n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        def can_arrive(m):\n",
    "            diff = []\n",
    "            for i in range(m):\n",
    "                if heights[i] < heights[i+1]:\n",
    "                    diff.append(heights[i+1]-heights[i])\n",
    "            diff.sort(reverse=True)\n",
    "            return sum(diff[ladders:]) <= bricks\n",
    "\n",
    "\n",
    "        l, r = 0, len(heights)-2\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if can_arrive(m+1):\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 通过时间：20.17.34\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        leaderque = PriorityQueue()\n",
    "        ans = 0\n",
    "        lenh = len(heights)\n",
    "        for i in range(lenh):\n",
    "            ans = i\n",
    "            if i == lenh - 1:\n",
    "                break\n",
    "            if heights[i] >= heights[i+1]:\n",
    "                continue\n",
    "            elif ladders > 0:\n",
    "                leaderque.put(heights[i+1] - heights[i])\n",
    "                ladders -= 1\n",
    "            elif leaderque.empty() == False:\n",
    "                now = leaderque.get()\n",
    "                if now < heights[i+1] - heights[i]:\n",
    "                    if bricks >= now:\n",
    "                        bricks -= now\n",
    "                        leaderque.put(heights[i+1] - heights[i])\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    if bricks >= heights[i+1] - heights[i]:\n",
    "                        bricks -= heights[i+1] - heights[i]\n",
    "                        leaderque.put(now)\n",
    "                    else:\n",
    "                        break\n",
    "            elif bricks >= heights[i+1] - heights[i]:\n",
    "                bricks -= heights[i+1] - heights[i]\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        res=0\n",
    "        ladders_hist=[]\n",
    "        heapq.heapify(ladders_hist)\n",
    "        for i in range(len(heights)-1):\n",
    "            \n",
    "            distance=heights[i+1]-heights[i]\n",
    "            if heights[i+1]<=heights[i]:\n",
    "                res+=1\n",
    "            elif ladders>0:\n",
    "                res+=1\n",
    "                heapq.heappush(ladders_hist,distance)\n",
    "                ladders-=1\n",
    "            elif ladders==0 and ladders_hist!=[]:\n",
    "                shortest=heapq.heappop(ladders_hist)\n",
    "                if shortest>distance:\n",
    "                    bricks-=distance\n",
    "                    heapq.heappush(ladders_hist,shortest)\n",
    "                    if bricks>=0:\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        return res\n",
    "                else:\n",
    "                    bricks-=shortest\n",
    "                    heapq.heappush(ladders_hist,distance)\n",
    "                    if bricks>=0:\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        return res\n",
    "            elif ladders==0:\n",
    "                bricks-=distance\n",
    "                if bricks>=0:\n",
    "                    res+=1\n",
    "                else:\n",
    "                    return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        heap = []\n",
    "        sum_brick = 0\n",
    "        n = len(heights)\n",
    "        for i in range(1, n):\n",
    "            cost = heights[i] - heights[i - 1]\n",
    "            if cost <= 0:\n",
    "                continue\n",
    "            heappush(heap, cost)\n",
    "            if len(heap) > ladders:\n",
    "                c = heappop(heap)\n",
    "                sum_brick += c\n",
    "                if sum_brick > bricks:\n",
    "                    return i - 1\n",
    "        return n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        q = [] \n",
    "        tot = 0 \n",
    "        n = len(heights) \n",
    "        for i in range(1, n):\n",
    "            d = heights[i] - heights[i-1]\n",
    "            if d > 0:\n",
    "                heapq.heappush(q, d) \n",
    "                if len(q) > ladders:\n",
    "                    x = heapq.heappop(q) \n",
    "                    tot += x \n",
    "                    if tot > bricks:\n",
    "                        return i - 1 \n",
    "        return n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        ladder_on = [] # 使用梯子跨过的高度（节省的砖头）；最小堆结构，堆顶是梯子历史使用的最小高度\n",
    "        brick_remain = bricks # 剩余还没用的砖头数量\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            if heights[i-1] >= heights[i]: continue\n",
    "\n",
    "            diff = heights[i] - heights[i-1]\n",
    "            if len(ladder_on) < ladders: # 还有梯子剩余，优先用梯子\n",
    "                heapq.heappush(ladder_on, diff)\n",
    "            elif len(ladder_on) > 0 and diff > ladder_on[0]: # 当前高差比梯子使用历史中的最小高差更大，把那架梯子用在这里更省砖头\n",
    "                brick_remain -= heapq.heappop(ladder_on) # 原来的那架梯子改为消耗砖头\n",
    "                if brick_remain < 0: return i-1 # 砖头不足以完成此操作，结束了\n",
    "                heapq.heappush(ladder_on, diff) # 当前位置使用梯子\n",
    "            else: # 使用砖头\n",
    "                brick_remain -= diff \n",
    "                if brick_remain < 0: return i-1 # 砖头不足以完成此操作，结束了\n",
    "\n",
    "        return len(heights) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        min_heap = []                                   # 最小堆\n",
    "\n",
    "        heapq.heapify(min_heap)\n",
    "        for i, (cur, nxt) in enumerate(zip(heights, heights[1:])):\n",
    "            gap = nxt - cur\n",
    "            if gap > 0:                                 # 只有向上时才用得到砖头梯子\n",
    "                heapq.heappush(min_heap, gap)           # 入最小堆\n",
    "                if len(min_heap) > ladders:             # 如果堆中保存的gap够梯子个数\n",
    "                    bricks -= heapq.heappop(min_heap)   # 从小gap到大gap弹出堆，先把砖头用完\n",
    "                    if bricks < 0:\n",
    "                        return i\n",
    "        return n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        \n",
    "        sortedList = SortedList()\n",
    "\n",
    "        i = 0\n",
    "        \n",
    "        minHeap = []\n",
    "        cur = 0\n",
    "        total = 0\n",
    "        j = 0\n",
    "        res = 0\n",
    "        while i < len(heights):\n",
    "            if i - 1 >= 0:\n",
    "                diff = heights[i] - heights[i-1]\n",
    "                if diff > 0:\n",
    "                    total += diff\n",
    "                    if len(minHeap) < ladders:\n",
    "                        heapq.heappush(minHeap, diff)\n",
    "                        cur += diff\n",
    "                    else:\n",
    "                        heapq.heappush(minHeap, diff)\n",
    "                        cur += diff\n",
    "                        cur -= heapq.heappop(minHeap)\n",
    "\n",
    "            \n",
    "            \n",
    "            if total - cur <= bricks:\n",
    "                res = max(res, i)\n",
    "            else:\n",
    "                break\n",
    "            i += 1\n",
    "        \n",
    "        return min(res, len(heights) - 1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        left = -1\n",
    "        right = len(heights)\n",
    "        offset = [0]  * len(heights)\n",
    "        for i in range(1, len(heights)):\n",
    "            offset[i] = max(0, heights[i] - heights[i-1]) \n",
    "        def check(m):\n",
    "            a = offset[:m+1]\n",
    "            a.sort()\n",
    "            if ladders >=len(a) or sum(a[:len(a) - ladders]) <=bricks:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = left + (right - left ) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return right -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        diff = [0] * n\n",
    "        for i in range(n - 1):\n",
    "            d = heights[i + 1] - heights[i]\n",
    "            if d > 0:\n",
    "                diff[i + 1] = d\n",
    "        def check(dist):  # dist 距离\n",
    "            ordered = sorted(diff[:dist + 1])\n",
    "            if dist + 1 <= ladders: return True\n",
    "            s = sum(ordered[:dist + 1 - ladders])\n",
    "            return s <= bricks\n",
    "        lo, hi = 0, n - 1\n",
    "        if check(hi): return hi\n",
    "        while lo < hi - 1:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        # 梯子可以爬过任何高度的楼顶。\n",
    "        # import heapq\n",
    "        # q = []\n",
    "        # n = len(heights)\n",
    "        # for i in range(1, n):\n",
    "        #     d_h = heights[i] - heights[i-1]\n",
    "        #     print(d_h)\n",
    "        #     if d_h < 0:\n",
    "        #         continue \n",
    "        #     elif d_h > 0 and d_h <= bricks: # 使用砖头\n",
    "        #         heapq.heappush(q, -d_h)\n",
    "        #         bricks -= d_h\n",
    "        #     elif d_h > 0 and d_h > bricks and ladders > 0:  # 试试看是否用梯子\n",
    "        #         if q[0]+bricks < d_h:  # 换了砖头还是翻不过去\n",
    "        #             ladders -= 1  # 直接用梯子翻过去\n",
    "        #             continue  # 不用梯子换砖头  \n",
    "        #         else:  # 梯子换砖头\n",
    "        #             ladders -= 1\n",
    "        #             bricks -= heapq.heappop(q)\n",
    "        #             bricks -= d_h\n",
    "        #     return i-1\n",
    "        # return n - 1\n",
    "\n",
    "\n",
    "\n",
    "        # hq = []\n",
    "        # for i in range(1, len(heights)):\n",
    "        #     diff = heights[i] - heights[i - 1]\n",
    "        #     # 只有当前楼层大于前一个楼层我们才需要抄家伙\n",
    "        #     if diff > 0:\n",
    "        #         # 通过负数模拟最大堆\n",
    "        #         heapq.heappush(hq, -diff)\n",
    "        #         # 优先减砖头\n",
    "        #         bricks -= diff\n",
    "        #         if bricks < 0:\n",
    "        #             # 砖头小于零时找梯子，有梯子交换，没梯子退出\n",
    "        #             if ladders:\n",
    "        #                 ladders -= 1\n",
    "        #                 # 最大砖头小号出堆，弥补砖头数量\n",
    "        #                 bricks -= heapq.heappop(hq)\n",
    "        #             else:\n",
    "        #                 return i - 1\n",
    "        # return n - 1\n",
    "\n",
    "\n",
    "\n",
    "        # 网友\n",
    "        #  # 准备一个大堆栈\n",
    "        queue = []\n",
    "        # 砖数\n",
    "        remainBricks = bricks\n",
    "        # 使用梯子的数量\n",
    "        usedLadders = 0\n",
    "        for i in range(1, len(heights)):\n",
    "            diff = heights[i] - heights[i-1]\n",
    "            if diff <= 0:\n",
    "                # 跳过的条件: 当前建筑比上一个建筑低\n",
    "                continue\n",
    "            # 把diff结果放到堆栈里, 但python默认是小堆栈, 所以我们只能放负数, 然后取出来的时候再取反\n",
    "            heapq.heappush(queue, -diff)\n",
    "            # 减去对应的砖数\n",
    "            remainBricks -= diff\n",
    "            # 如果还有砖就继续\n",
    "            if (remainBricks >= 0):\n",
    "                continue\n",
    "            # 如果没梯子了就直接返回\n",
    "            if (usedLadders >= ladders):\n",
    "                return i - 1\n",
    "            # 把砖块拿回来改用梯子, 这里取出来的是 最小的负数, 所以需要取反, 变成最大的数\n",
    "            remainBricks += -heapq.heappop(queue)\n",
    "            # 使用梯子数量+1\n",
    "            usedLadders += 1\n",
    "        # 如果能走到这里, 说明所有的剪枝都能走过\n",
    "        return len(heights) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        import queue\n",
    "        q = queue.PriorityQueue()\n",
    "        res = 0\n",
    "        for i in range(len(heights)-1):\n",
    "            #print(i,ladders,bricks)\n",
    "            satisfied = True\n",
    "            if heights[i+1] > heights[i]:\n",
    "                q.put(heights[i+1]-heights[i])\n",
    "                while q.qsize() > ladders and not q.empty():\n",
    "                    min_gap = q.get()\n",
    "                    if bricks < min_gap:\n",
    "                        ladders -= 1\n",
    "                        if ladders >= 0:\n",
    "                            satisfied = True\n",
    "                        else:\n",
    "                            satisfied = False\n",
    "                    else:\n",
    "                        bricks -= min_gap\n",
    "                        if bricks >= 0:\n",
    "                            satisfied = True\n",
    "                        else:\n",
    "                            satisfied = False\n",
    "            if not satisfied:\n",
    "                break\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        import queue\n",
    "        q = queue.PriorityQueue()\n",
    "        res = 0\n",
    "        for i in range(len(heights)-1):\n",
    "            #print(i,ladders,bricks)\n",
    "            if heights[i+1] > heights[i]:\n",
    "                q.put(heights[i+1]-heights[i])\n",
    "                if q.qsize() > ladders:\n",
    "                    min_gap = q.get()\n",
    "                    bricks -= min_gap\n",
    "                    if bricks < 0:\n",
    "                        break\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#可以到达的最远建筑，贪心优先队列，输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1输出：4；输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2输出：7\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights, bricks, ladders):\n",
    "        hq = []\n",
    "        for i in range(1, len(heights)):\n",
    "            diff = heights[i] - heights[i - 1]\n",
    "            if diff > 0:# 只有当前楼层大于前一个楼层我们才需要抄家伙\n",
    "                heapq.heappush(hq, -diff)# 通过负数模拟最大堆\n",
    "                bricks -= diff # 优先减砖头\n",
    "                if bricks < 0:\n",
    "                    # 砖头小于零时找梯子，有梯子交换，没梯子退出\n",
    "                    if ladders:\n",
    "                        ladders -= 1\n",
    "                        bricks -= heapq.heappop(hq)# 最大砖头小号出堆，弥补砖头数量\n",
    "                    else:return i - 1\n",
    "        return len(heights) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        # 每次使用砖头，再使用梯子，\n",
    "        q = []\n",
    "        n = len(heights)\n",
    "        for i in range(1, n):\n",
    "            diff = heights[i] - heights[i-1]\n",
    "            if diff <= 0:\n",
    "                continue\n",
    "            bricks -= diff # 优先使用砖头\n",
    "            heapq.heappush(q, -diff) # 使用最大堆\n",
    "            if bricks < 0:\n",
    "                if ladders: # 如果有梯子，找到耗费最多砖头的跳跃，用梯子替换\n",
    "                    ladders -= 1\n",
    "                    if q:\n",
    "                        bricks -= heapq.heappop(q)\n",
    "                else:\n",
    "                    return i - 1\n",
    "        return n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        heap = []\n",
    "        for i in range(n-1):\n",
    "            if(heights[i] >= heights[i+1]):\n",
    "                continue\n",
    "            else:\n",
    "                if(bricks >= heights[i+1] - heights[i]):\n",
    "                    bricks -= heights[i+1] - heights[i]\n",
    "                    heapq.heappush(heap,heights[i] - heights[i+1])\n",
    "                else:\n",
    "                    if(ladders > 0):\n",
    "                        if(len(heap) > 0 and heights[i+1] - heights[i] < -heap[0]):\n",
    "                            bricks -= heapq.heappop(heap)\n",
    "                            bricks -= heights[i+1] - heights[i]\n",
    "                            heapq.heappush(heap, heights[i] - heights[i+1])  \n",
    "                        ladders -= 1\n",
    "                    else:\n",
    "                         return i            \n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        pq = []\n",
    "        s = 0\n",
    "        for i,x in enumerate(heights[:-1]):\n",
    "            if heights[i] < heights[i + 1]:\n",
    "                heappush(pq,heights[i + 1] - heights[i])\n",
    "                if len(pq) > ladders:\n",
    "                    s += heappop(pq)\n",
    "                    if s > bricks:\n",
    "                        return i\n",
    "        return len(heights) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: \n",
    "        def check(self, heights: List[int], bricks: int, ladders: int, m: int):\n",
    "            heap = []\n",
    "            sum = 0\n",
    "            for i in range(m):\n",
    "                g = heights[i + 1] - heights[i]\n",
    "                if g > 0:\n",
    "                    if len(heap) < ladders:\n",
    "                        heappush(heap, g)\n",
    "                    elif len(heap) > 0:\n",
    "                        heappush(heap, g)\n",
    "                        sum += heappop(heap)\n",
    "                    else:\n",
    "                        sum += g\n",
    "            return sum <= bricks\n",
    "        l, r = -1, len(heights)\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, heights, bricks, ladders, m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        def check(x):\n",
    "            arr = []\n",
    "            for i in range(1,min(n,x + 1)):\n",
    "                arr.append(max(0,heights[i] - heights[i - 1]))   \n",
    "            arr.sort()\n",
    "            res = sum(arr[:-ladders]) if ladders != 0 else sum(arr)\n",
    "            return res <= bricks \n",
    "        l,r = 0,n - 1\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        left = -1\n",
    "        right = len(heights)\n",
    "        offset = [0]  * len(heights)\n",
    "        for i in range(1, len(heights)):\n",
    "            offset[i] = max(0, heights[i] - heights[i-1]) \n",
    "        def check(m):\n",
    "            a = offset[:m+1]\n",
    "            a.sort()\n",
    "            if ladders >=len(a) or sum(a[:len(a) - ladders]) <=bricks:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        while left + 1 < right:\n",
    "            mid = left + (right - left ) // 2\n",
    "            print(mid)\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return right - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "\n",
    "        heap=[]\n",
    "        n=len(heights)\n",
    "        for i in range(1,n):\n",
    "            diff=heights[i]-heights[i-1]\n",
    "            if diff<=0:continue\n",
    "            if bricks>=diff:\n",
    "                bricks-=diff\n",
    "                heappush(heap,-diff)\n",
    "            elif ladders:\n",
    "                ladders-=1\n",
    "                if heap and -heap[0]>diff:\n",
    "                    bricks+=-heappop(heap)-diff\n",
    "                    heappush(heap,-diff)\n",
    "            else:\n",
    "                return i-1\n",
    "            print(i,bricks,ladders)\n",
    "        \n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "\n",
    "        heap = []\n",
    "        for i in range(1, len(heights)):\n",
    "            dh = heights[i] - heights[i - 1]\n",
    "            print(dh)\n",
    "            if dh > 0:\n",
    "                if len(heap) < ladders:\n",
    "                    heapq.heappush(heap, dh)\n",
    "                else:\n",
    "                    if ladders > 0 and heap[0] < dh: \n",
    "                        bricks -= heapq.heappop(heap)\n",
    "                        heapq.heappush(heap, dh)\n",
    "                    else:\n",
    "                        bricks -= dh\n",
    "                    if bricks < 0:\n",
    "                        return i - 1\n",
    "        return len(heights) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = 0\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        st = SortedList()\n",
    "        for i in range(n-1):\n",
    "            if(heights[i] >= heights[i+1]):\n",
    "                continue\n",
    "            else:\n",
    "                if(bricks >= heights[i+1] - heights[i]):\n",
    "                    bricks -= heights[i+1] - heights[i]\n",
    "                    st.add(heights[i+1] - heights[i])\n",
    "                else:\n",
    "                    if(ladders > 0):\n",
    "                        if(len(st) > 0 and heights[i+1] - heights[i] < st[-1]):\n",
    "                            bricks += st.pop()\n",
    "                            bricks -= heights[i+1] - heights[i]\n",
    "                            st.add(heights[i+1] - heights[i])    \n",
    "                        ladders -= 1\n",
    "                    else:\n",
    "                         return i            \n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = 0\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        st = SortedList()\n",
    "        for i in range(n-1):\n",
    "            if(heights[i] >= heights[i+1]):\n",
    "                continue\n",
    "            else:\n",
    "                if(bricks >= heights[i+1] - heights[i]):\n",
    "                    bricks -= heights[i+1] - heights[i]\n",
    "                    st.add(heights[i+1] - heights[i])\n",
    "                else:\n",
    "                    if(ladders > 0):\n",
    "                        if(len(st) == 0 or heights[i+1] - heights[i] >= st[-1]):\n",
    "                            ladders -= 1\n",
    "                        else:\n",
    "                            bricks += st.pop()\n",
    "                            bricks -= heights[i+1] - heights[i]\n",
    "                            st.add(heights[i+1] - heights[i])    \n",
    "                            ladders -= 1\n",
    "                    else:\n",
    "                         return i            \n",
    "        return n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        leaderque = PriorityQueue()\n",
    "        ans = 0\n",
    "        lenh = len(heights)\n",
    "        for i in range(lenh):\n",
    "            ans = i\n",
    "            print(i)\n",
    "            if i == lenh - 1:\n",
    "                break\n",
    "            if heights[i] >= heights[i+1]:\n",
    "                continue\n",
    "            elif ladders > 0:\n",
    "                leaderque.put(heights[i+1] - heights[i])\n",
    "                ladders -= 1\n",
    "            elif leaderque.empty() == False:\n",
    "                now = leaderque.get()\n",
    "                if now < heights[i+1] - heights[i]:\n",
    "                    if bricks >= now:\n",
    "                        bricks -= now\n",
    "                        leaderque.put(heights[i+1] - heights[i])\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    if bricks >= heights[i+1] - heights[i]:\n",
    "                        bricks -= heights[i+1] - heights[i]\n",
    "                        leaderque.put(now)\n",
    "                    else:\n",
    "                        break\n",
    "            elif bricks >= heights[i+1] - heights[i]:\n",
    "                bricks -= heights[i+1] - heights[i]\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "\n",
    "        \n",
    "        l, r = 0, len(heights) - 1\n",
    "        def check(x):\n",
    "            cur = []\n",
    "            for i in range(1, x + 1):\n",
    "                heapq.heappush(cur, -(max(0, heights[i] - heights[i - 1])))\n",
    "            b, l = bricks, ladders\n",
    "            heapq.heapify(cur)\n",
    "            while cur:\n",
    "                c = -heapq.heappop(cur)\n",
    "                if c:\n",
    "                    if l > 0:\n",
    "                        l -= 1\n",
    "                    else:\n",
    "                        if b >= c:\n",
    "                            b -= c\n",
    "                        else:\n",
    "                            return False\n",
    "            return True\n",
    "        \n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        '''\n",
    "            二分答案法+贪心思想\n",
    "            思路：\n",
    "                二分答案，mid作为能到达的最远建筑物。难点在于如何判断 以mid作为答案时，使用\n",
    "                有限的砖和梯子数量，能达到要求。\n",
    "            贪心思想：1个梯子能走任意高度，1块砖只能提高1个单位长度。\n",
    "                所以对于所有向上走的时候，gap差距最大的，优先使用梯子，梯子用完之后，才使用砖\n",
    "        '''\n",
    "\n",
    "        def check(i: int) -> bool:\n",
    "            gap = []\n",
    "            for x, y in pairwise(heights[0 : i + 1]):\n",
    "                if x < y:\n",
    "                    gap.append(y - x)\n",
    "            b = bricks\n",
    "            gap.sort(reverse=True) # 从大到小排序\n",
    "            for i in range(ladders, len(gap)):\n",
    "                if b >= gap[i]:\n",
    "                    b -= gap[i]\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        l, r = 0, len(heights)\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return ans\n",
    "\n",
    "\n",
    "    # 暴力解，超时\n",
    "    def furthestBuilding1(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        @cache\n",
    "        def f(i: int, bricks: int, ladders: int) -> int:\n",
    "            if i == len(heights):\n",
    "                return i\n",
    "            if i != 0 and heights[i] <= heights[i - 1]:\n",
    "                return f(i + 1, bricks, ladders)\n",
    "            elif i != 0:\n",
    "                # 用梯子，还是铺砖，两种选择\n",
    "                p1 = p2 = 0\n",
    "                if heights[i] - heights[i - 1] <= bricks:\n",
    "                    p1 = f(i + 1, bricks - (heights[i] - heights[i - 1]), ladders)\n",
    "                if ladders > 0:\n",
    "                    p2 = f(i + 1, bricks, ladders - 1)\n",
    "                return max(p1, p2, i)\n",
    "            return i\n",
    "            \n",
    "        return f(1, bricks, ladders) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        arr=[]\n",
    "        for i in range(1,len(heights)):\n",
    "            tmp=heights[i]-heights[i-1]\n",
    "            if tmp>0:\n",
    "                heapq.heappush(arr,[-tmp,i])\n",
    "                if bricks-tmp>=0:\n",
    "                    # print(\"zheli\",tmp)\n",
    "                    bricks-=tmp\n",
    "                    # print(\"zheli\",bricks)\n",
    "                else:\n",
    "                    if ladders<=0:\n",
    "                        return i-1\n",
    "                    now=heapq.heappop(arr)\n",
    "                    if now[1]!=i:\n",
    "                        bricks-=tmp\n",
    "                        bricks+=-now[0]\n",
    "                    # print(bricks)\n",
    "                    ladders-=1\n",
    "        return len(heights)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        if ladders >= n - 1:\n",
    "            return n - 1\n",
    "        nums = []\n",
    "        last = heights[0]\n",
    "        for h in heights:\n",
    "            diff = h - last\n",
    "            nums.append(0 if diff <= 0 else diff)\n",
    "            last = h\n",
    "        # [4,2,7,6,9,14,12]\n",
    "        # [0,0,5,0,3, 5, 0]\n",
    "\n",
    "        def achieve(nums, bricks, ladders):\n",
    "            nums.sort(reverse=True)\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    break\n",
    "                if ladders > 0:\n",
    "                    ladders -= 1\n",
    "                elif bricks >= nums[i]:\n",
    "                    bricks -= nums[i]\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            flag = achieve(nums[:mid + 1], bricks, ladders)\n",
    "            if flag:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        left = 1\n",
    "        right = len(heights)\n",
    "\n",
    "        diff = []\n",
    "        for i in range(1, len(heights)):\n",
    "            diff.append(heights[i] - heights[i - 1])\n",
    "\n",
    "\n",
    "        def check(target):\n",
    "            aim = [ele for ele in diff[:target - 1] if ele > 0]\n",
    "            aim.sort(reverse = True)\n",
    "            if ladders >= len(aim):\n",
    "                return True\n",
    "            sum_ = sum(aim)\n",
    "\n",
    "            for k in range(ladders):\n",
    "                sum_ -= aim[k]\n",
    "            \n",
    "            return sum_ <= bricks\n",
    "            \n",
    "            \n",
    "            \n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "\n",
    "        def can_arrive(m):\n",
    "            diff = diffs[:m].copy()\n",
    "            diff.sort(reverse=True)\n",
    "            return sum(diff[ladders:]) <= bricks\n",
    "\n",
    "        \n",
    "        diffs = [max(heights[i+1]-heights[i], 0) for i in range(len(heights)-1)]\n",
    "\n",
    "        l, r = 0, len(heights)-2\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if can_arrive(m+1):\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        if ladders >= n - 1:\n",
    "            return n - 1\n",
    "        nums = []\n",
    "        last = heights[0]\n",
    "        for h in heights:\n",
    "            diff = h - last\n",
    "            nums.append(0 if diff <= 0 else diff)\n",
    "            last = h\n",
    "        # [4,2,7,6,9,14,12]\n",
    "        # [0,0,5,0,3, 5, 0]\n",
    "\n",
    "        def achieve(nums, bricks, ladders):\n",
    "            nums.sort(reverse=True)\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    break\n",
    "                if ladders > 0:\n",
    "                    ladders -= 1\n",
    "                elif bricks >= nums[i]:\n",
    "                    bricks -= nums[i]\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        l, r = ladders, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            flag = achieve(nums[:mid + 1], bricks, ladders)\n",
    "            if flag:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as pq\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        diff = [0 for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            diff[i] = max(0, heights[i] - heights[i-1])\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while left < right:\n",
    "            mid = (right - left + 1) // 2 + left\n",
    "            sumBricks = [0 for _ in range(mid)]\n",
    "            Sum = 0\n",
    "            for i in range(mid+1):\n",
    "                pq.heappush(sumBricks, -diff[i])\n",
    "                Sum += diff[i]\n",
    "            for i in range(ladders):\n",
    "                Sum += pq.heappop(sumBricks)\n",
    "            if bricks < Sum:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        # first having an array to keep track of the differences between two positions\n",
    "        ht_diffs = []\n",
    "        n = len(heights)\n",
    "        for i in range(n - 1):\n",
    "            ht_diffs.append(max(0, heights[i + 1] - heights[i]))\n",
    "        cur_brick_sum = 0\n",
    "        pq = []\n",
    "        heapq.heapify(pq)\n",
    "        \n",
    "        for i, ht_diff in enumerate(ht_diffs):\n",
    "            heapq.heappush(pq, ht_diff)\n",
    "            if len(pq) > ladders:\n",
    "                small_brick_diff = heapq.heappop(pq)\n",
    "                cur_brick_sum += small_brick_diff\n",
    "                if cur_brick_sum > bricks:\n",
    "                    return i\n",
    "        return n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: \n",
    "        def check(self, diff: List[int], bricks: int, ladders: int, m: int):\n",
    "            heap = []\n",
    "            sum = 0\n",
    "            for i in range(m):\n",
    "                g = diff[i]\n",
    "                if g > 0:\n",
    "                    if len(heap) < ladders:\n",
    "                        heappush(heap, g)\n",
    "                    elif len(heap) > 0:\n",
    "                        heappush(heap, g)\n",
    "                        sum += heappop(heap)\n",
    "                    else:\n",
    "                        sum += g\n",
    "            return sum <= bricks\n",
    "\n",
    "        diff = []\n",
    "        for i in range(len(heights) - 1):\n",
    "            diff.append(heights[i + 1] - heights[i])\n",
    "        \n",
    "        l, r = -1, len(heights)\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, diff, bricks, ladders, m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        diff = [max(heights[i]-heights[i-1], 0) for i in range(1, n)]\n",
    "        \n",
    "        def check(m):\n",
    "            b, l = bricks, ladders\n",
    "            q = diff[:m]\n",
    "            heapify(q)\n",
    "            while q and b >= q[0]:\n",
    "                b -= heappop(q)\n",
    "            return l >= len(q)\n",
    "\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            m = (i + j) // 2 + 1\n",
    "            if check(m):\n",
    "                i = m\n",
    "            else:\n",
    "                j = m - 1\n",
    "        return j\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "\n",
    "        last = [max(y-x,0)for x,y in pairwise(heights)]\n",
    "    \n",
    "        def check(h):\n",
    "            return h<=ladders or sum(sorted(last[:h])[:h-ladders])<=bricks\n",
    "        left = 0\n",
    "        right = len(last)\n",
    "        while left<=right:\n",
    "            mid =( left+right)>>1\n",
    "            if check(mid):\n",
    "                left =mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        def jd(diff, bricks, ladders, mid):\n",
    "            temp = sorted(diff[0: mid + 1])\n",
    "            # print(temp)\n",
    "            if len(temp) <= ladders or sum(temp[:len(temp) - ladders]) <= bricks:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        diff = [0 for i in range(0, len(heights)-1)]\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            diff[i-1] = max(0, heights[i] - heights[i-1])\n",
    "            \n",
    "        left = 0\n",
    "        right = len(diff)\n",
    "        mid = left + (right - left)//2\n",
    "        while left < right:\n",
    "            if jd(diff, bricks, ladders, mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "            # print(left, right, mid)\n",
    "            mid = left + (right - left) // 2\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        n = len(heights)\n",
    "        diff = [max(heights[i]-heights[i-1], 0) for i in range(1, n)]\n",
    "        \n",
    "        def check(m):\n",
    "            b, l = bricks, ladders\n",
    "            q = diff[:m]\n",
    "            heapify(q)\n",
    "            while q and b >= q[0]:\n",
    "                b -= heappop(q)\n",
    "            return l >= len(q)\n",
    "\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            m = (i + j) // 2 + 1\n",
    "            if check(m):\n",
    "                i = m\n",
    "            else:\n",
    "                j = m - 1\n",
    "        return j\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        low=0\n",
    "        high=len(heights)-1\n",
    "        while low < high:\n",
    "            mid=ceil((low+high)/2)\n",
    "            arr=[]\n",
    "            for i in range(1,mid+1):\n",
    "                diff=heights[i]-heights[i-1]\n",
    "                if diff>0:\n",
    "                    arr.append(diff)\n",
    "            flag=True\n",
    "            if len(arr)>ladders:\n",
    "                ar=sorted(arr)\n",
    "                if sum(ar[i] for i in range(len(ar)-ladders))>bricks:\n",
    "                    flag=False\n",
    "            if flag:\n",
    "                low=mid\n",
    "            else:\n",
    "                high=mid-1\n",
    "        return low\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        # 以下解法超时！！猜测是堆中去n大值耗时太久。\n",
    "        position = [] # 每个gap的右边位置\n",
    "        gap= [] # gap的大小\n",
    "\n",
    "        for i in range(1,len(heights)):\n",
    "            h = heights[i] - heights[i-1]\n",
    "            if h > 0: # 存在gap要上升\n",
    "                gap.append(h)\n",
    "                position.append(i)\n",
    "\n",
    "        n = ladders\n",
    "        m = bricks\n",
    "\n",
    "        # first = 0\n",
    "        # second = 0 \n",
    "        # 不只是维护2个尖端，而是n个最大值。想到了堆，只要知道n个最大值的和，用总sum减去和，与bricks比较，就能看能不能跨越这道gap。\n",
    "        \n",
    "        import heapq\n",
    "        summary = 0\n",
    "        heap = []\n",
    "        if n > len(gap):\n",
    "            return len(heights)-1\n",
    "    \n",
    "        for i in range(n):\n",
    "            summary += gap[i]\n",
    "            heapq.heappush(heap, gap[i])\n",
    "            \n",
    "        # end = len(heights)\n",
    "        summ = 0\n",
    "        for i in range(n, len(gap)):\n",
    "            # summary += gap[i]\n",
    "            heapq.heappush(heap, gap[i])\n",
    "            # summin = sum(heapq.nlargest(n, heap)) # 找到n个最大值的和\n",
    "            # 其实只需要维护n最大值的堆就行，把小的扔掉都用砖头试试，杀鸡焉用牛刀，得保存大的用梯子。\n",
    "            # 要找的是剩下的gap能不能用砖头填补的空缺\n",
    "            if len(heap) > n:\n",
    "                summ += heapq.heappop(heap)\n",
    "\n",
    "            if summ > bricks:\n",
    "                end = i\n",
    "                res = position[end] - 1\n",
    "                return res\n",
    "        \n",
    "        return len(heights)-1\n",
    "        # \n",
    "        \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        left, right = 0, len(heights)-1\n",
    "        diff = []\n",
    "        for i in range(1,right+1):\n",
    "            diff.append(max(0,heights[i]-heights[i-1]))\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if mid <= ladders:\n",
    "                left = mid+1\n",
    "                continue\n",
    "            tmp = sorted(diff[:mid])\n",
    "            total = sum(tmp[:mid-ladders])\n",
    "            if total <= bricks:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\r\n",
    "        # # 使用@cache超出内存占用\r\n",
    "        # # 使用@lru_cache超时\r\n",
    "        # @lru_cache\r\n",
    "        # def helper(idx, restBricks,restLadders):\r\n",
    "        #     if idx+1<len(heights):\r\n",
    "        #         if heights[idx]>=heights[idx+1]:\r\n",
    "        #             return helper(idx+1,restBricks,restLadders)\r\n",
    "        #         else:\r\n",
    "        #             p=idx\r\n",
    "        #             if heights[idx+1]-heights[idx]<=restBricks:\r\n",
    "        #                 p = helper(idx+1,restBricks-(heights[idx+1]-heights[idx]),restLadders)\r\n",
    "        #             if restLadders:\r\n",
    "        #                 p=max(p,helper(idx+1,restBricks,restLadders-1))\r\n",
    "        #             return p\r\n",
    "        #     else:\r\n",
    "        #         return idx\r\n",
    "\r\n",
    "        # ret = helper(0,bricks,ladders)\r\n",
    "        # helper.cache_clear()\r\n",
    "        # return ret\r\n",
    "\r\n",
    "        # # 贪心+优先队列\r\n",
    "        # hp=[]\r\n",
    "        # cnt= 0\r\n",
    "        # n=len(heights)\r\n",
    "        # for i in range(1,n):\r\n",
    "        #     if (diff:=heights[i]-heights[i-1])>0:\r\n",
    "        #         heapq.heappush(hp,diff)\r\n",
    "        #         if len(hp)>ladders:\r\n",
    "        #             minVal=heapq.heappop(hp)\r\n",
    "        #             cnt+=minVal\r\n",
    "        #             if cnt>bricks:\r\n",
    "        #                 return i-1\r\n",
    "        # return n-1\r\n",
    "\r\n",
    "        # 二分\r\n",
    "        n = len(heights)\r\n",
    "        # 注意diffs的写法\r\n",
    "        diffs = [max(0, heights[i]-heights[i-1]) for i in range(1, n)]\r\n",
    "\r\n",
    "        left, right = 0, n-1\r\n",
    "\r\n",
    "        while left < right:\r\n",
    "            mid = (left+right+1) >> 1\r\n",
    "            sortedDiffs = sorted(diffs[:mid], reverse=True)\r\n",
    "            # numBricks= sum(sortedDiffs[:-ladders])\r\n",
    "\r\n",
    "            if sum(sortedDiffs[ladders:]) <= bricks:\r\n",
    "                left = mid\r\n",
    "            else:\r\n",
    "                right = mid-1\r\n",
    "        return left\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights, bricks: int, ladders: int):\n",
    "        cha = []\n",
    "        weizhi = []\n",
    "\n",
    "        for index in range(0, len(heights) - 1):\n",
    "            if heights[index+1] > heights[index]:\n",
    "                cha.append(heights[index+1] - heights[index])\n",
    "                weizhi.append(index)\n",
    "\n",
    "        if not cha:\n",
    "            return len(heights) - 1\n",
    "\n",
    "        if not bricks and not ladders:\n",
    "            return weizhi[0]\n",
    "\n",
    "        def isfind(tmp):\n",
    "            heapq.heapify(tmp)\n",
    "            l = heapq.nlargest(ladders, tmp)\n",
    "            if bricks < sum(tmp) - sum(l):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        left = 0\n",
    "        right = len(cha) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1)//2\n",
    "            if isfind(cha[0:mid + 1]):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return weizhi[right+1] if right+1<len(weizhi) else len(heights) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:\n",
    "        left, right = 0, len(heights)-1\n",
    "        diff = []\n",
    "        for i in range(1,right+1):\n",
    "            diff.append(heights[i]-heights[i-1])\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if mid <= ladders:\n",
    "                left = mid+1\n",
    "                continue\n",
    "            tmp = sorted(diff[:mid])\n",
    "            total = 0\n",
    "            for i in range(mid-ladders):\n",
    "                if tmp[i] > 0:\n",
    "                    total += tmp[i]\n",
    "            if total<=bricks:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return right\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
